package com.example.algorithm.greedy;

/**
 * 在一排多米诺骨牌中，A[i] 和 B[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。
 * （一个多米诺是两个从 1 到 6 的数字同列平铺形成的 该平铺的每一半上都有一个数字。）
 *
 *  我们可以旋转第 i 张多米诺，使得 A[i] 和 B[i] 的值交换。
 *
 *  返回能使 A 中所有值或者 B 中所有值都相同的最小旋转次数。
 *
 * 示例 1：
 * 输入：A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
 * 输出：2
 *
 * 示例 2：
 * 输入：A = [3,5,1,2,3], B = [3,6,3,3,4]
 * 输出：-1
 */
public class Leetcode1007_MinDominoRotations {
    public static void main(String[] args) {
        int[] A = {2,3,2,1,1,1,2,2};
        int[] B = {2,1,2,1,1,3,1,1};
        System.out.println(minDominoRotations1(A, B));
    }

    /**
     * 解法一:暴力法
     *
     * 1.首先判断是否存在这样的旋转：
     * 统计1——6这六个数字的出现次数
     * 在A中出现的次数;在B中出现的次数
     * 在骨牌出现的次数（在多少个骨牌中出现过，骨牌上下都出现需记作一次）
     *
     * 2.再求解最小旋转次数
     * @param A
     * @param B
     * @return
     */
    public static int minDominoRotations1(int[] A, int[] B) {
        // 声明三个6个元素的数组分别用于存放A,B,A|B(A或者B 即多米诺骨牌出现)数组中出现1-6的次数
        int[] countA = new int[6];
        int[] countB = new int[6];
        int[] countAB = new int[6];


        for (int i = 0; i < A.length; i++) {
            // 分别统计A,B数组数字1-6出现的次数
            countA[A[i] - 1]++;
            countB[B[i] - 1]++;

            // 统计多米诺骨牌出现1-6的次数，
            // 当A[i] == B[i]时,该数字只统计一次，不同则需要分别统计
            countAB[A[i]-1]++;
            if (A[i] != B[i]) {
                countAB[B[i] - 1]++;
            }
        }

        // 遍历骨牌统计表找到出现次数等于骨牌总数的数字
        for (int i = 0; i < countAB.length; i++) {
            if (countAB[i] == A.length)
                return A.length - Math.max(countA[i], countB[i]);
        }
        // 如果没有找到出现次数等于骨牌总数的数字，说明无法通过旋转来达到一半全是一个数
        return -1;
    }

    /**
     * 解法二:贪心算法
     *
     * 思路：
     * 从最终得到的结果出发
     * 每张多米诺骨牌上只有两个数字，如果存在行相等则旋转的最终结果
     * • A中的数字都是A[0] 或者A中的数字都是B[0]
     * • B中的数字都是A[0] 或者B中的数字都是B[0]
     * 故只需考察A[0]、B[0]在其他骨牌上的出现情况
     * 若某骨牌中不存在，则提前终止，无需浏览后面的骨牌
     * @param A
     * @param B
     * @return
     */
    public static int minDominoRotations2(int[] A, int[] B) {
        // 判断能否将A中或B中全部元素变成A[0]
        int rotations = check(A[0], A, B);
        // 若能，返回旋转次数少的那个，不用再检查B[0]
        // 如果A[0] == B[0]，再检查B[0]没有意义
        // 如果A[0] != B[0]，仅当骨牌中只有A[0]、B[0]两个数字才能将A中或B中全部元素变成B[0]，此时最小旋转次数将和A[0]一样
        if (rotations != -1 || A[0] == B[0]) {
            return rotations;
        } else {// 若不能，并且A[0] != B[0]，再判断能否将A中或B中全部元素变成B[0]
            return check(B[0], A, B);
        }

    }

    // 检查将A或者B中元素全部变成x需要多少次旋转
    public static int check(int x, int[] A, int[] B) {
        int rotationsA=0, rotationsB=0;
        // 遍历⻣骨牌判断是否能完成任务（在A中完成或者在B中完成）
        for (int i = 0; i < A.length; i++) {
            // 上下都和x相同时，说明无法通过旋转使得上部分或者下部分完全相同
            if (A[i] != x && B[i] != x) {
                return -1;
            } else if (A[i] != x) {
                rotationsA++;
            } else if (B[i]!=x){
                rotationsB++;
            }
        }
        // 返回最⼩小旋转次数
        return Math.min(rotationsA, rotationsB);
    }

}
